MuItiprocessor, shared resource computer systems are commonly employed where high speed throughput is required. Typically, such systems are characterized by a plurality of processors, which function as masters, and share a common bus. A plurality of input/output devices, which function as slaves, also share the common bus so that the masters and slaves may communicate with one another in well known fashion. Such a system is illustrated in simplified form in FIG. 1 wherein the masters are depicted by the blocks labeled M0, M1, etc. and the slaves are depicted by the blocks labeled S1, S2, etc. Since only one master and one slave may communicate with each other at any given point in time, it is common for such systems to employ some technique where the masters compete among themselves for bus control. An arbitration technique is usually employed for determining which master should control the bus during any given data cycle. Typically, an arbitration circuit employing some type of arbitration method determines which master should control the bus next. Various arbitration methods are known which award bus control based on, for example, assigned priority of each competing master, each master's previous bus usage level, or based upon a round-robin technique, to name but a few. Irrespective of the particular arbitration method employed, a problem arises when the slave selected by the master to perform a certain task is either busy or slow to respond. Typically, the slave informs the master having control of the bus of this situation. In the art, this situation is generally referred to as either a "busy", or a "wait". It is said that the slave either "busies the transaction" or "waits the transaction", since the process of the master requesting service from the slave and communicating with the slave to retrieve data is known as a "transaction."
There are at least two reasons why a slave may busy a transaction. First, the slave may be slow in performing the required transactions. Here, slow is a relative term. In some systems, slow may mean several microseconds, and in others, a few hundred nanoseconds. Second, a slave may be busy doing something else, or may not have any additional resources to devote to the incoming transaction, and therefore be unable to respond to the master immediately.
One known method of handling busy and/or slow responding slaves in the prior art is for the master having bus control ("winning master") to hold control of the bus until the slave has performed the service requested by the winning master and has provided the resulting data. In another known method, the slave raises a flag when it is busy, and the winning master holds control of the bus and polls the slave until it becomes available. The winning master then maintains control of the bus until the slave has completed the requested service. It will be appreciated that the time spent for the winning master waiting for the slave to either become available or finish its task represents unproductive time insofar as bus usage and sharing of system resources are concerned. Thus, these methods waste bus bandwidth since other masters could gainfully employ the bus, but for the action of the winning master in waiting for the slave.
In still another known method, once a master has been busied, it releases the bus. The master then rearbitrates for bus control, and if the slave that it is attempting to access is busy, the master again releases the bus and must later rearbitrate for the bus and again attempt to access the slave. This method suffers from the need to assure forward progress, i.e., that all requests will eventually be serviced, otherwise deadlock and/or starvation may occur. In addition, this method suffers from an essentially unlimited upper bound on the number of "wasted" transactions that are issued until the slave is able to respond.
In yet another known method, the bus is freed by the winning master after service has been requested from the slave, and interrupts are employed to signal this master that the slave is either ready or has completed its task. While this method overcomes the drawbacks of the first two methods described above, it suffers from the same drawback of the third method described above. Moreover, it may require the use of process swaps or may require several interrupt lines on the bus. It may also require the use of polling by the master to determine which slave interrupted the master. Thus, this method is expensive not only in the resources that must be allocated to service the interrupt, but also in terms of the time required to effect process swaps and/or determine which slave caused the interrupt. Moreover, this method may add overhead to the system since it requires combining arbitration and interrupt driven methodologies.
There is yet another known method, known as a "split transaction", wherein the master issues a request for service and at a later indeterminate time, the slave responds with the requested service by issuing a "return" transaction. This method still doesn't solve the "busy" case, and also requires the slave to be able to "master" transactions.
There is therefore a need in the art for a method of reducing the amount of wasted bandwidth resulting from slow responding slaves, and which overcomes all of the foregoing problems of the prior art, yet is simple and relatively inexpensive to implement. The present invention achieves these goals.